from typing import List
from Tree import TreeNode
"""
def process(preorder, inorder):
    if not preorder:
        return None
    parent = TreeNode(preorder[0])
    i = inorder.index(parent.val)
    li = inorder[:i]
    if li:
        lp = preorder[1:1+len(li)]
        parent.left = process(lp, li)
    ri = inorder[i+1:] if i+1 < len(preorder) else []
    if ri:
        rp = preorder[i+1:] if ri else preorder[1:]
        parent.right = process(rp, ri)
    return parent
"""

class Solution:
    
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def process(pres,pree,ins,ine):
            if pres > pree:
                return None
            parent = TreeNode(preorder[pres])
            k = d[parent.val]
            left_num = k - ins
            parent.left = process(pres+1,pres+left_num,ins,k-1)
            parent.right = process(pres+left_num+1,pree,k+1,ine)
            return parent
        d = {v:i for i,v in enumerate(inorder)}
        return process(0,len(preorder)-1,0,len(inorder)-1)
        

if __name__ == '__main__':
    c = Solution()
    preorder = [1,2,3]
    inorder = [3,2,1]
    e = c.buildTree(preorder, inorder)
    print(e.bfs_show())